1. Field of the Invention
This invention relates to a cryptographic key recovery system and, more particularly, to a method and apparatus for verifying the correctness of key recovery information within a cryptographic key recovery system.
2. Description of the Related Art
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories. Symmetric (or private key) encryption systems such as the Data Encryption Standard (DES) system use the same secret key for both encrypting and decrypting messages. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir and Adleman.
Asymmetric encryption systems are generally more computationally intensive than symmetric encryption systems, but have the advantage that they do not require a secure channel for the transmission of encryption keys. For this reason, asymmetric encryption systems are often used for the one-time transport of highly sensitive data such as symmetric encryption keys.
Data encryption systems of all types have attracted the attention of government intelligence agencies and law enforcement agencies, since the same cryptographic strength that prevents decryption by unauthorized third parties also prevents decryption by intelligence or law enforcement officials having a legitimate reason for wanting to access the plaintext data. Because of such concerns, governments have either prohibited the use or export of strong encryption systems or have conditioned their approval on the use of weakened keys that are susceptible to key-exhaustion attacks (i.e., systematically testing all possible keys until the right one is found). Such weak encryption systems have the obvious disadvantage that they are just as vulnerable to unauthorized third parties as they are to authorized government officials.
Various cryptographic key recovery systems have recently been proposed as a compromise between the demands of communicating parties for privacy in electronic communications and the demands of law enforcement agencies for access to such communications when necessary to uncover crimes or threats to national security. Generally, in such key recovery systems, all or part of the key used by the communicating parties is made available to one or more key recovery agents, either by actually giving key portions to the key recovery agents (in which case the key portions are said to be "escrowed") or by providing sufficient information in the communication itself (as by encrypting the key portions) to allow the key recovery agents to regenerate the key portions. Key recovery agents would reveal the escrowed or regenerated key portions to a requesting law enforcement agent only upon presentation of proper evidence of authority, such as a court order authorizing the interception. The use of multiple key recovery agents, all of which must cooperate to recover the key, minimizes the possibility that a law enforcement agent can improperly recover a key by using a corrupt key recovery agent.
Key recovery systems serve the communicants' interest in privacy, since their encryption system retains its full strength against third parties and does not have to be weakened to comply with domestic restrictions on encryption or to meet export requirements. At the same, key recovery systems serve the legitimate needs of law enforcement by permitting the interception of encrypted communications in circumstances where unencrypted communications have previously been intercepted (as where a court order has been obtained).
In addition to serving the needs of law enforcement, key recovery systems find application in purely private contexts. Thus, organizations may be concerned about employees using strong encryption of crucial data where keys are not recoverable. Loss of keys may result in loss of important data.
An important aspect of key recovery systems is the method used to ensure that correct recovery information is provided. If the recovery information provided is not correct, either through unintentional error, or deliberate attempt to conceal, the functionality of the key recovery system can be thwarted. Validation can be provided in several ways, including direct checking by the participants, checking by the trustees, and checking by the recovery entity. Correctness can also be ensured by redundant calculation and disclosure of the recovery information by more than one of the communicating parties.
Verification methods have several desirable properties. The verification method should not require communication with parties external to the given communication, either at installation, or during message creation and transmission. The method of verification should ensure correctness even if some (but not all) of the communicating parties deliberately attempt to provide incorrect recovery information. The verification method should minimize the required computations, and transmission overhead associated with the verification.
Key recovery systems of various types are described in D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow Encryption Systems", Communications of the ACM, vol. 39, no. 3, Mar. 1996, pp. 34-40, incorporated herein by reference. Several specific key recovery systems are noted below.
Micali et al. U.S. Pat. Nos. 5,276,737 ("Micali I") and 5,315,658 ("Micali II") describe a "fair" public key cryptosystem in which the private key of a public/private key pair is broken into "shares" that are given to "trustees". The "breaking" is done in such a manner that: (1) the shares of all trustees (or a predetermined quorum) are required to reconstruct the key; and (2) each trustee can individually verify the correctness of his share. When all the trustees have certified the correctness of their share, the user's public key (corresponding to the escrowed private key) is certified by a key management center. Upon a predetermined requests the trustees provide their shares to a law enforcement agent or other recovering entity, who then reconstructs the private key from the shares and, with the private key, is able to monitor communications to the user. In this key recovery system, verification is done by the key management center and the trustees. This method of verification is undesirable, in that it requires prior communications with the trustees and key management center.
In another key recovery system, described in U.S. Pat. No. 5,557,346 to Lipner et al., the sender splits a session key into first and second session key portions by setting the first session key portion equal to a random number and setting the second session key portion equal to the XOR product of the random number and the session key. The sender creates a law enforcement access field (LEAF) by encrypting the respective session key portions with the public encryption keys of first and second key recovery agents and concatenating the two encryption products. The sender also creates a LEAF verification string (LVS) by concatenating the original session key portions and encrypts this using the session key to form an encrypted LEAF verification string (ELVS). Finally, the sender transmits an encrypted message, together with the LEAF and ELVS, to the receiver.
Before decrypting the encrypted message, the receiver regenerates the LEAF to verify that the sender has created a proper LEAF that would actually permit recovery of the session key through the key recovery agents. This is done by decrypting the ELVS to obtain the session key portions and then encrypting the respective session key portions with the public encryption keys of first and second key recovery agents. If the receiver succeeds in regenerating the transmitted LEAF in this manner, it concludes that the LEAF is genuine and proceeds to decrypt the message. Otherwise, it concludes that the LEAF is corrupt and does not proceed with the decryption step.
In this key recovery system, the verification of key recovery information is done by the receiver, which does avoid communication with the trustees or key management center. It does however require several public key encryption and decryption operations for every communication session, which is expensive in terms of computation and message size.
The copending application of R. Gennaro et al., Ser. No. 08/725,102, a filed Oct. 2, 1996, and entitled "Two-Phase Cryptographic Key Recovery System" (attorney docket P0996104), describes an alternative method of key recovery called SKR, which permits a portion of the key recovery information to be generated once and then used for multiple encrypted data communications sessions and encrypted file applications. In particular, the mentioned portion of the key recovery information that is generated just once is the portion that requires public key encryption operations. Hence, SKR provides a way of reducing the costly public key encryption operations required of other key recovery methods.
The Gennaro et al. application also describes a verification mode in which the communicating parties Alice and Bob each produce SKR recovery blocks independently, without checking the other's so produced blocks. In this mode, if at least one side is correctly configured, all required recovery information is correctly produced. In addition, both Alice and Bob are free to include any optional recovery fields without causing a false invalidation of what the other sent. One limitation of this verification mode, however, is that it cannot be used in non-interactive communications.
The SKR method of key recovery and verification described in the Gennaro et al. application is computationally efficient, as it provides for extensive caching of the recovery information, and requires no explicit verification. Its principal disadvantages are: (1) that it does not provide verification for non-interactive communications without requiring the receiver to perform public key operations; and (2) that it requires the transmission of additional secret information to Bob to allow him to perform verification, increasing the size of required communications.
The recent paper of E. Verheule B. -J. Koops and H. C. A. van Tilborg entitled "Binding Cryptography, A Fraud-Detectible Alternative to Key-Escrow Proposals" (1996), published at http://cwis.kub.nl/.sup..about. frw/people/koops/binding.htm, and the paper of E. Verheul and H. C. A. van Tilborg entitled "Binding the ElGamal Encryption Scheme" (1996), published at http://cwis.kub.nl/.sup..about. frw/people/koops/bindtech.htm, present an alternative for validation of key recovery information. The papers describe a method in which a disinterested observer can verify that something encrypted under a receiver's public key is the same as something encrypted under an agent's public key. If the "something" is a session key or part of a session key, as is the case in key recovery fields, the observer can use this to validate the encrypted recovery data. Unlike the previous methods of verification, however, this method provides no way for the observer to verify that the encrypted fields actually contain correct information; instead, the observer only verifies that the encryptions contain the same secret.
Still other methods of verifiably providing key recovery use variants of the Diffie-Hellman (DH) key agreement protocol. By way of background, the Diffie-Hellman key agreement protocol is a procedure whereby two parties may establish a shared secret value (from which a symmetric encryption key may be derived) by exchanging only public values over a communications channel. The protocol was originally described at page 649 of W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol. IT-22, no. 6, Nov. 1976, pp. 644-654, and in U.S. Pat. No. 4,200,770, both incorporated herein by reference.
In the two-party interactive form of the protocol, each party generates (e.g., pseudorandomly) a secret value x which it keeps to itself. Each party then generates a public value EQU y=g.sup.x mod p
where x is the secret value of that party, p is a prime modulus and g is a generator over the Galois field GF(p) consisting of the set of integers {0, 1, 2, . . . p-1}, and transmits the public value to the other party. Thereafter, each party generates a shared secret value EQU z=y.sup.x mod p
where x is its own secret value, y is the public value received from the other party, and p is defined as above. By virtue of the properties of modulo arithmetic, the shared secret values z generated by the two parties are the same.
The parties may derive a symmetric encryption key directly from the shared secret value z, as by extracting the required number of bits. Alternatively, the parties may perform a further operation on the shared secret value such as concatenating it with another value and hashing the concatenation result, as described in the copending application of S. M. Matyas et al., Ser. No. 08/736,774, filed Oct. 25, 1996, entitled "Method and Apparatus for Establishing an Authenticated Shared Secret Value Between a Pair of Users", incorporated herein by reference.
The security of this procedure relies on the apparent fact that, for appropriate choices of p and g, it is computationally infeasible to obtain either the secret values x or the shared value z from the public values y exchanged between the parties. Although exponentiation over a finite field was used in the above example, in general any suitable functions y(x) and z(x, y) may be used that have the commutative property
z(x1, y(x2))=z(x2, y(x1))
for any x1 and x2 and have the noninvertibility property mentioned above.
One such method of verifiably providing key recovery based on establishing a shared common Diffie-Hellman key was proposed by Dorothy E. Denning in "To Tap or Not to Tap", Communications of the ACM, vol. 36, no. 3, Mar. 1993, pp. 26-33. In this paper she proposed an escrow system based on a three-party variation of Diffie-Hellman described in section 22.1 of B. Schneier, Applied Cryptography (2d ed. 1996) as well as in the original Diffie et al. (1976) article cited above. In this method of key recovery, the verification of the recovery information can be inherent in the receiver's decryption of the information encrypted under the shared session key k.
The system proposed by Denning works as follows: Let Alice be the sender, Bob be the receiver, and Ted the trustee in order around the three-party circle. Let their respective secret parts be x, y, and z. In the first round, Alice sends to Bob g.sup.x mod p, Bob sends to Ted g.sup.y mod p, and Ted sends to Alice g.sup.z mod p. In the second round, Alice sends to Bob g.sup.zx mod p, Bob sends to Ted g.sup.xy mod p, and Ted sends to Alice g.sup.yz mod p. From these values, everyone can calculate k=g.sup.xyz. If Alice sends something to Bob encrypted with k, Bob knows that Ted can calculate k and decrypt it also. (If Alice is dishonest, and does not want Ted to be able to calculate k correctly she could send an incorrect value of g.sup.zx mod p to Bob, and Bob would be unable to detect the error. This can be fixed by having Bob verify this value directly with Ted as an additional exchange of messages after the second round.)
This method has the advantage of being able to send encrypted recovery information to both Bob and Ted with a single encrypted field, thus reducing the size of data and the number of calculations. However, this method has the disadvantage of requiring communication with the trustee prior to transmission of the message to the receiver.
In a paper entitled "Alternatives to RSA Using Diffie-Hellman with DSS" (1996), published at http://www.cylink.com/products/security/rsa/rsa-dss2.htm, Cylink Corporation proposed a method similar to Denning's, but not requiring interactive communication with the trustee. Using the same example, let Alice be the senders Bob be the receiver, and Ted be the trustee, and let their respective secret parts be x, y, and z.
Prior to any communication, Ted calculates a shared Diffie-Hellman key v with Alice based on Alice's public key (g.sup.x mod p), and his private key Z, as follows: EQU u=g.sup.xz mod p EQU v=g.sup.u mod p
Ted publishes v as a public key shared between Alice and him. For communication with Bob, Alice can calculate a key k as:
k=g.sup.yv mod p
Both Bob and Ted can calculate k, so if Alice sends something to Bob encrypted with k, she knows that Ted can also read it. In addition, Bob can verify this escrow, as he knows that Ted published the shared key v, and Ted can therefore calculate k. However, the disadvantage of this method is that it requires Alice to obtain a published shared key from Ted prior to communication with Bob.